import javax.swing.tree.TreeNode;
import java.util.HashMap;

/**
 * Created by L.jp
 * Description:输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 * User: 86189
 * Date: 2021-12-23
 * Time: 18:23
 */
//解题思路：
//二叉树都是递归定义的，所以递归操作是比较常见的做法
//首先明白：子结构怎么理解，可以理解成子结构是原树的子树(或者一部分)
//也就是说，B要是A的子结构，B的根节点+左子树+右子树，都在A中存在且构成树形结构
//比较的过程要分为两步
//1. 先确定起始位置
//2. 在确定从该位置开始，后续的左右子树的内容是否一致
 class TreeNode1{
    int val = 0;
    TreeNode1 left = null;
    TreeNode1 right = null;
    public TreeNode1(int val) {
        this.val = val;
    }
}
public class Solution {
     public boolean isSame(TreeNode1 root1,TreeNode1 root2){
         //如果根节点的值相等，而且遍历完了另一颗子树,那么只有这个子树的结构跟另一颗子树结构相等才会返回true,否则只要有一个节点不相等就会返回根节点去判断左子树和右子树
         if(root2==null){
             return true;
         }
         //判断了主树的每个节点说明没有找到相等的结构，如果找到了相等的结构的话就会直接返回true,而不会遍历整棵树
         if(root1==null){
             return false;
         }
         //还要判断每个节点的值是否相等
         if(root1.val!=root2.val){
             return  false;
         }
        return  isSame(root1.left,root2.left) && isSame(root1.right,root2.right);//一定要使得左子树、右子树的结构跟另一颗子树的结构相等才可以
     }
    public boolean HasSubtree(TreeNode1 root1, TreeNode1 root2) {
         //首先判断两个根节点是否为空
         if(root1==null  || root2==null) {
             return false;
         }
         boolean result=false;//记录最终的结果
         //根节点不为空，那么就要判断根节点的值是否相等
         if(root1.val==root2.val){
             //相等就进入这个根节点的子树，再进行判断
            result= isSame(root1,root2);
         }
         //如果这个根节点的值不相等的话就要递归进入他的左子树和右子树
        if(!result){
            result=HasSubtree(root1.left,root2);
        }
        //如果左子树的结构还是和子树不相等，那么就再判断右子树
        if(!result){
            result=HasSubtree(root1.right,root2);
        }
        //最终返回结果
        return  result;
    }
}
